//
//  ProblemOffer46.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/26.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 46. 把数字翻译成字符串
 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

 示例 1:
     输入: 12258
     输出: 5
     解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
 提示：0 <= num < 231
 */
@objcMembers class ProblemOffer46: NSObject {
    func solution() {
        print(translateNum(12258))
    }
    
    /*
     12258
     计算最后一个数字8，他有2种可能性：
     1> 8作为独立的使用，那么f(n) = f(n-1)
     2> 58作为独立使用，但是58不符合要求
     那么就需要就算f(n-1)即可 f(n) = f(n-1)
     如果是前面那个数是1，变成18，那么f(n) = f(n-1) + f(n-2)
     总结：
     f(n) = f(n-1)
     if (满足条件) {
        f(n) += f(n-2)
     }
     
     */
    func translateNum(_ num: Int) -> Int {
        let str = Array(String(num))
        var dp:[Int] = Array(repeating: -1, count: str.count)
        
        let n = translateNumDp(str, dp.count-1, &dp)
        print(dp)
        return n
    }
    
    func translateNumDp(_ str: [Character], _ i: Int, _ dp: inout [Int]) -> Int {
        if dp[i] != -1 {
            return dp[i]
        }
        if i == 0 {
            dp[i] = 1
            return dp[i]
        }
        dp[i] = translateNumDp(str, i-1, &dp)
        if str[i-1] == "1" || (str[i-1] == "2" && str[i] <= "5") {
            if i >= 2 {
                dp[i] += translateNumDp(str, i-2, &dp)
            } else {
                dp[i] += 1
            }
            
        }
        return dp[i]
    }
}
